A communication network is generally recognized as an interconnection of forwarding devices that process and send packets of information across the network. The network can either be an Internet or an Intranet and the forwarding devices can be gateways, bridges, switches, or routers. One objective of the forwarding devices is to reliably forward the packets from a source to a destination.
In whatever form, a forwarding device typically includes one or more lookup tables. An incoming destination address (or other search key) is derived from a packet of information and compared against entries stored within the lookup table. Resulting from the search, the associated packet of information may be processed according to a set of rules and sent to an appropriate output port of the forwarding device. As links of the network change, routing protocols exchange information among the forwarding devices in order to change the entries stored within the corresponding lookup tables. This change will modify not only the entries within the lookup table, but also the next-hop identifiers or other associated data pointed to by the addresses of those entries. Routing through the forwarding devices can, therefore, be changed dynamically as links go down and come back up in various parts of the Internet or Intranet.
High-speed packet classification algorithms, which scale to large multi-field databases, have recently become a widespread requirement for a variety of applications, such as network security appliances, quality of service filtering and load balancers. For classifying packets, a forwarding device (e.g., a router) may employ a classification database (also called a policy database), which has several access control lists (ACLs). Each ACL consists of several rules that may be applied to incoming and/or outgoing packets. While the syntax of these rules varies based on the router vendor, the semantics of the rules allows similar classification information to be specified—i.e., the rules allow various patterns to be defined based on the packet header. Furthermore, a set of actions is specified for each rule, and these actions are applied to all packets that match the rule.
Designing highly scalable algorithms that support millions of rules and several million searches per second has been, and continues to be, an important stream of research. Several advances in algorithmic approaches that use off-chip random access memories have been made in the past. However, in the past few years, the industry has increasingly employed Ternary Content Addressable Memories (TCAMs) for performing packet classification. A large class of current and next generation systems that require a few ten to a few hundred thousand rules have adopted TCAMs for packet classification at multi-gigabit speeds.
A TCAM is a memory device that stores data as a massive array of fixed-width ternary entries. A ternary entry may be described as a string of bits, where each bit is either a 0, 1 or x (don't care). Memory searches are performed quickly in a TCAM by comparing a search key against all TCAM entries in parallel. When the content stored in a TCAM memory location does not match the search key, the TCAM device returns a “no match” indication. If a match is found, however, the TCAM device returns a “match” indication by asserting the match line for that entry.
Two main characteristics that make TCAMs suitable for router design include deterministic search throughput and deterministic capacity. As of this writing, current TCAMs can support up to 133 million searches per second for 144-bit wide search keys. Current TCAMs can also store up to 128K ternary entries (that are 144 bits wide) in a single device. While TCAMs are well suited for performing high-speed searches on databases with ternary entries, certain limitations tend to reduce the efficiency of the TCAM memory device.
For example, TCAM efficiency is often limited because multiple TCAM entries are typically needed to store a rule having one or more range fields (e.g., the source and destination port fields in IP router ACLs usually have ranges). Since ranges cannot be directly stored in a TCAM, they are usually converted into a set of prefixes, and each prefix is stored in a separate TCAM entry. When the range-to-prefix expansion technique is applied to source and destination port fields, which are 16 bits wide, a rule with a single range field can consume up to 30 TCAM entries (in the worst case). Larger range fields would obviously consume even more TCAM entries, thus, further reducing the efficiency and storage capacity of the TCAM device.
Therefore, a need remains for an improved method for encoding a range field within a TCAM device, using fewer TCAM entries than used by conventional encoding schemes for the same bit width. Such a method could be used to increase the efficiency and storage capacity of pre-existing TCAM devices without hardware modification.